# -*- coding:utf-8 -*-
from collections import defaultdict

"""
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
"""


class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        slist = list(s)
        fsame = findsame(slist)
        maxnum = findmaxnum(fsame, slist)
        for k, v in maxnum.items():
            numlist = fsame[k]
            if v[0] > 0:
                if v[1] == v[2]:
                    sr = "".join(slist[v[1]-int(v[0]/2):v[1]+int(v[0]/2)+1])
                else:
                    sr = "".join(slist[v[2] - int(v[0] / 2)+1:v[1] + int(v[0] / 2)])
            else:
                sr = "".join(slist[numlist[0]:numlist[0] + 1])
            return sr


def deletesingle(d):
    """
    删除掉没有重复字母的元素

    :param d: 
    :return: 
    """
    del_key = []
    for k, v in d.items():
        if len(v) < 2:
            del_key.append(k)
    if len(d.keys()) > 1:
        for i in del_key:
            d.pop(i)
    return d


def findsame(slist):
    """
    找出相等的数字

    :param i: 
    :param slist: 
    :return: 
    """
    d = defaultdict(list)
    for k, va in [(v, i) for i, v in enumerate(slist)]:
        d[k].append(va)
    d = deletesingle(d)
    return d


def findmaxnum(fsame, flist):
    """
    找出最大的回文数字
    
    :param fsame: 
    :param flist: 
    :return: 
    """
    fmax = {}
    if len(fsame.keys()) == 1 and len(list(fsame.values())[0]) == 1:
        for k in fsame.keys():
            fmax[k] = [1,0,0]
    else:
        for k, v in fsame.items():
            for i in range(len(v) - 1, 0, -1):
                for j in range(0, i):
                    num = 0
                    num = ispalindromic(v[j], v[i], flist, num)
                    if k in fmax.keys() and fmax[k][0] > num[0]:
                        pass
                    else:
                        fmax[k] = num
            numlist = list(fmax.values())
            maxnum = max(numlist)
            delnum = []
            for m, n in fmax.items():
                if n[0] != maxnum[0]:
                    delnum.append(m)
            for a in delnum:
                fmax.pop(a)
    return fmax


def ispalindromic(start, end, flist, num):
    """
    判断该起始位置是否是回文结构
    
    :param start: 
    :param end: 
    :return: 
    """
    if start > end:
        return [num, start, end]
    if start == end:
        return [num + 1, start, end]
    if flist[start] == flist[end]:
        num += 2
        start += 1
        end -= 1
        return ispalindromic(start, end, flist, num)
    else:
        num = -1
        return [num, -1, -1]


s1 = "ccc"
s2 = "cbbd"
s3 = "abcda"
s4 = "a"
s5 = "abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa"
s = Solution()
a = s.longestPalindrome(s1)
b = s.longestPalindrome(s2)
c = s.longestPalindrome(s3)
d = s.longestPalindrome(s4)
e = s.longestPalindrome(s5)
print(a)
print(b)
print(c)
print(d)
print(e)
